package cn.whdream.datastructure.search;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import cn.whdream.datastructure.sort.Util;

/**
 * 
 * @author blackjuly
 * 二分查找，数组必须为有序数组
 */
public class BinarySearch {
	public static void main(String[] args) {
		int arr[] = {1,8,10,89,1000,1000,1234};
		int index = binarySearch(arr, 0, arr.length, 88);
		if(index == -1) {
			System.out.println("没有找到");
		}else {
			System.out.println("坐标："+index);
		}
		List<Integer> list = binarySearch2(arr,  0, arr.length, 1000);
		System.out.println("查找的数组结果");
		System.out.println(list);
	}
	
	/**
	 * 自己的思路
	 * @param arr 数组
	 * @param left 坐标索引
	 * @param right 右边索引
	 * @param findVal 需要找到的值
	 * @return -1 没有找到 其他则是找到了
	 */
	private static int binarySearch(int[] arr,int left,int right,int findVal){
		int mid = (left + right)/2;
		//相等则说明找到了
		if(arr[mid] == findVal) {
			return mid;
		}
		//左右相加除 2 后，还等于 left eg: 3 + 4 =7; 7/2=3 该情况，说明已经处理到相邻的两个数字了，相邻之后仍然没有找到，则说明找不到了
		if(mid == left) {
			return -1;
		}
		//中间值比找的值大，则缩小范围找 到 左边区域找    （ps:应该排除 mid的值）
		if(arr[mid] > findVal) {
			return binarySearch(arr, left, mid, findVal);
		}
		//缩小到右边找	
		return binarySearch(arr, mid, right, findVal);
			
	}
	/**
	 * 类似尚硅谷官方的写法（看起来这种更优，递归的次数更少
	 */
	private static int binarySearch1(int[] arr,int left,int right,int findVal){
		//左边都大于右边
		if(left > right) {
			return -1;
		}
		
		int mid = (left + right)/2;
		//相等则说明找到了
		if(arr[mid] == findVal) {
			return mid;
		}
		
		//中间值比找的值大，则缩小范围找 到 左边区域找 ，此处一定要把 mid的值 传入 left 时 mid+1 传入right时 mid-1；否则第一个判断不成立
		if(arr[mid] > findVal) {
			return binarySearch(arr, left, mid-1, findVal);
		}
		//缩小到右边找	
		return binarySearch(arr, mid+1, right, findVal);
			
	}
	/**
	 * 查找多个相同的
	 */
	private static List<Integer> binarySearch2(int[] arr,int left,int right,int findVal){
		List<Integer> list = new ArrayList<Integer>();
		//左边都大于右边
		if(left > right) {
			return new ArrayList<Integer>();
		}
		
		int mid = (left + right)/2;
		//相等则说明找到了
		if(arr[mid] == findVal) {
			list.add(mid);
			int temp = mid -1;
			while(true) {
				if(temp <0) {
					break;
				}
				if(arr[temp] == findVal) {
					list.add(temp);
				}
				temp--;
			}
			temp = mid+1;
			while(true) {
				if(temp > arr.length-1) {
					break;
				}
				if(arr[temp] == findVal) {
					list.add(temp);
				}
				temp++;
			}
			return list;
		}
		
		//中间值比找的值大，则缩小范围找 到 左边区域找 ，此处一定要把 mid的值 传入 left 时 mid+1 传入right时 mid-1；否则第一个判断不成立
		if(arr[mid] > findVal) {
			return binarySearch2(arr, left, mid-1, findVal);
		}
		//缩小到右边找	
		return binarySearch2(arr, mid+1, right, findVal);
			
	}
		
	
}
